import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 19182
 * Date: 2025-10-19
 * Time: 21:36
 */
public class RBTree {
    static class RBTreeNode{
        public int val;
        public COLOR color;
        public RBTreeNode parent;
        public RBTreeNode left;
        public RBTreeNode right;
        public RBTreeNode(int val){
            this.val = val;
            //默认插入红色节点，还有一半几率不用变色，如果插入黑色，那么必须要改变所有路径
            color = COLOR.RED;
        }
    }
    public RBTreeNode root;
    public boolean insert(int val){
        RBTreeNode node = new RBTreeNode(val);
        if(root == null){
            root = node;
            //祖宗节点必须是黑色
            node.color = COLOR.BLACK;
            return true;
        }
        RBTreeNode cur = root;
        RBTreeNode parent = null;
        while(cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val){
                System.out.println("插入节点重复！");
                return false;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
        if(parent.val < val){
            parent.right = node;
        }else{
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        //父节点是红色，新节点插入默认也是红色，连续红色违反规则
        while(parent != null && parent.color == COLOR.RED){
            RBTreeNode grandFather = parent.parent;
            if(grandFather.left == parent){
                RBTreeNode uncle = grandFather.right;
                if(uncle != null && uncle.color == COLOR.RED){
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    parent = cur.parent;
                }else{
                    //情况三：uncle不存在，或者uncle节点是黑色, 现在parent是左子树，cur是parent右子树节点先左旋，再右旋
                    if(parent.right == cur){
                        RotateLeft(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    //情况二:uncle不存在，或者uncle存在并且是黑色，parent左子树，cur是parent的左子树节点，只需要右旋
                    RotateRight(grandFather);
                    parent.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                }

            }else{
                RBTreeNode uncle = grandFather.left;
                if(uncle != null && uncle.color == COLOR.RED){
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    parent = cur.parent;
                }else{
                    //情况三：uncle不存在，或者uncle节点是黑色, 现在parent是右子树，cur是parent左子树节点先右旋，再左旋
                    if(parent.left == cur){
                        RotateRight(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    //情况二:uncle不存在，或者uncle存在并且是黑色，parent右子树，cur是parent的右子树节点，只需要左旋
                    RotateLeft(grandFather);
                    parent.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                }
            }
        }
        root.color = COLOR.BLACK;
        return true;
    }
    private void RotateRight(RBTreeNode parent){
        RBTreeNode subL = parent.left;
        RBTreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        if(subLR != null){
            subLR.parent = parent;
        }
        RBTreeNode pParent = parent.parent;
        parent.parent = subL;

        if(root == parent){ //如果parent是祖宗节点， 那么上面肯定没有其他节点，直接把subL替换成祖宗节点即可
            root = subL;
            root.parent = null;
        }else{  //如果不是，判断parent是pParent的左节点还是右节点，把subL与pParent建立关系
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
    }
    private void RotateLeft(RBTreeNode parent){
        RBTreeNode subR = parent.right;
        RBTreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if(subRL != null){  //这里有可能为空
            subRL.parent = parent;
        }
        RBTreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent){ //如果是祖宗节点，那么subR作为祖宗节点
            root = subR;
            root.parent = null;
        }else{  //不是，判断parent是pParent的左节点还是右节点，把subR和pParent建立关系
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
    }
    public boolean isRBTree(){
        if(root == null){
            return true;
        }
        if(root.color != COLOR.BLACK){
            System.out.println("违反了性质：根节点必须是黑色的！");
            return false;
        }
        int blackNum = 0;
        RBTreeNode cur = root;
        while(cur != null){
            if(cur.color == COLOR.BLACK){
                blackNum++;
            }
            cur = cur.left;
        }
        return checkRedColor(root) && checkBlackNum(root, 0, blackNum);
    }
    private boolean checkRedColor(RBTreeNode root){
        if(root == null){
            return true;
        }
        RBTreeNode parent = root.parent;
        if(parent != null && parent.color == COLOR.RED && parent.color == root.color){
            return false;
        }
        return checkRedColor(root.left) && checkRedColor(root.right);
    }
    private boolean checkBlackNum(RBTreeNode root, int pathBlackNum, int blackNum){
        //有可能是空树
        if(root == null){
            return true;
        }
        //如果存在root, 那么就先计算路径黑色节点
        if(root.color == COLOR.BLACK){
            pathBlackNum++;
        }
        //必须左子树和右子树节点都为空才是空节点，表示一个路径走完了，单独一个为空也可能不是空节点
        if(root.left == null && root.right == null){
            if(pathBlackNum != blackNum){
                System.out.println("每条路径的黑色节点个数不一样");
                return false;
            }
        }

        return checkBlackNum(root.left, pathBlackNum, blackNum) && checkBlackNum(root.right, pathBlackNum, blackNum);
    }
    public void inorder(RBTreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        // 测试用例1：基本插入测试
        System.out.println("=== 测试用例1：基本插入测试 ===");
        RBTree tree1 = new RBTree();
        int[] nums1 = {10, 20, 5, 15, 30};
        for (int num : nums1) {
            tree1.insert(num);
        }
        System.out.println("中序遍历结果（值+颜色）：");
        tree1.inorder(tree1.root);
        System.out.println("\n是否为有效的红黑树：" + (tree1.isRBTree() ? "是" : "否") + "\n");

        // 测试用例2：连续插入同一方向节点（测试旋转功能）
        System.out.println("=== 测试用例2：连续插入右子树节点 ===");
        RBTree tree2 = new RBTree();
        int[] nums2 = {10, 20, 30, 40, 50, 60}; // 连续向右插入
        for (int num : nums2) {
            tree2.insert(num);
        }
        System.out.println("中序遍历结果（值+颜色）：");
        tree2.inorder(tree2.root);
        System.out.println("\n是否为有效的红黑树：" + (tree2.isRBTree() ? "是" : "否") + "\n");

        // 测试用例3：随机插入测试（更多场景覆盖）
        System.out.println("=== 测试用例3：随机插入测试 ===");
        RBTree tree3 = new RBTree();
        Random random = new Random();
        int[] nums3 = new int[15];
        for (int i = 0; i < 15; i++) {
            nums3[i] = random.nextInt(100); // 生成0-99的随机数
        }
        System.out.println("插入的随机数序列：");
        for (int num : nums3) {
            System.out.print(num + " ");
            tree3.insert(num);
        }
        System.out.println("\n中序遍历结果（值+颜色）：");
        tree3.inorder(tree3.root);
        System.out.println("\n是否为有效的红黑树：" + (tree3.isRBTree() ? "是" : "否"));
    }


}
